Ein Schlüsselproblem beim parallelen Rechnen in grossen Prozessornetzwerken ist die effiziente Kommunikation der Prozessoren untereinander. Wir haben, hauptsächlich für Gitternetzwerke, verschiedene Fragestellungen unter (relativ einfachen) Annahmen untersucht, z.B.

• Sortieren von Schlüsseln, die auf den Netzwerken verteilt sind
• statisches Realisieren von vorgegebenen Permutationen von Paketen
• Verschicken von Einzel- und Mehrfachnachrichten (randomisiert und deterministisch)
• Permutationsrouting auf Busstrukturen bzw. rekonfigurierbaren Netzwerken
• Laufzeitverhalten versus Größe der lokalen Speicher (Ziel: Hot-Potato-Routing)
• Praxistauglichkeit der Verfahren

In Zukunft wollen wir uns noch intensiver um praxistaugliche Verfahren bemühen, dabei auch Aspekte wie Fehlertoleranz untersuchen sowie Algorithmen aus anderen Bereichen (z.B. Bildverarbeitung) effizient auf Gitternetzwerke übertragen.

Veröffentlichungen

M.Kaufmann, H.Schröder, J.Sibeyn: ``Asymptotically Optimal and Practical Routing on Reconfigurable Meshes'', Special Issue of 'Parallel Processing Letters', Vol. 5(1) , pp. 81-95, 1995.

M.Kaufmann, J.F.Sibeyn, T. Suel: ``Beyond the Bisection Bound: Fast Ranking and Counting on Meshes'', Proc. 3rd European Symposium on Algorithms (ESA'95), LNCS 979, pp. 75-88, Springer-Verlag, 1995.

B.Chlebus, M.Kaufmann, J.F.Sibeyn: ``Deterministic Permutation Routing on Meshes'', in print for Journal of Algorithms.

M. Kaufmann, R. Raman, J.F. Sibeyn, ``Randomized Routing on Meshes with Buses,'' in print for Algorithmica.

Kaufmann, M., U. Meyer, J.F. Sibeyn, ``Matrix Transpose on Meshes: Theory and Practice,'' in print for Computers and Artificial Intelligence, Vol. 16, 1997.